package jmotioncapture.util;

/**
 * 
 * @author Will Tang
 * 
 */
public class Sort {
	/**
	 * Swaps the content of two elements in the <code>list</code> array.
	 * 
	 * @param list
	 *            array to perform swap
	 * @param i
	 *            index of the first element
	 * @param j
	 *            index of the second element
	 */
	public static <T> void swap(T[] list, int i, int j) {
		T temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}

	/**
	 * Use the BubbleSort algorithm to sort the <code>list</code> array in
	 * ascending order.
	 * 
	 * @param ary
	 *            the array to be sorted
	 * @return the sorted array
	 */
	public static <T extends Comparable<? super T>> T[] bubbleSort(T[] list) {
		boolean swapped;
		do {
			swapped = false;
			for (int i = 0; i < list.length - 1; i++) {
				if (list[i].compareTo(list[i + 1]) > 0) {
					swap(list, i, i + 1);
					swapped = true;
				}
			}
		} while (swapped);

		return list;
	}

	/**
	 * Use the HeapSort algorithm to sort the <code>list</code> array in
	 * ascending order.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @return the sorted array
	 */
	public static <T extends Comparable<? super T>> T[] heapSort(T[] list) {
		int HeapSize = list.length - 1;

		for (int i = HeapSize / 2; i > 0; i--) {
			Heapify(list, i, HeapSize);
		}

		for (int i = list.length - 1; i > 1; i--) {
			swap(list, i, 1);
			HeapSize--;
			Heapify(list, 1, HeapSize);
		}

		return list;
	}

	/**
	 * A function used by the HeapSort algorithm.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @param i
	 * @param HeapSize
	 */
	protected static <T extends Comparable<? super T>> void Heapify(T[] list,
			int i, int HeapSize) {
		int left = 2 * i, right = 2 * i + 1;
		int largest;

		if ((left <= HeapSize) && (list[left].compareTo(list[i])) > 0)
			largest = left;
		else
			largest = i;

		if ((right <= HeapSize) && (list[right].compareTo(list[largest]) > 0))
			largest = right;

		if (largest != i) {
			swap(list, i, largest);
			Heapify(list, largest, HeapSize);
		}
	}

	/**
	 * Use the QuickSort algorithm to sort the array <code>list</code> array
	 * in ascending order.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @return the sorted array
	 */
	public static <T extends Comparable<? super T>> T[] quickSort(T[] list) {
		quickSort(list, 0, list.length - 1);

		return list;
	}

	/**
	 * The recursive function used by the QuickSort algorithm.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @param low
	 * @param high
	 */
	protected static <T extends Comparable<? super T>> void quickSort(T[] list,
			int low, int high) {
		if (low >= high)
			return;
		else if (low == high - 1) {
			if (list[low].compareTo(list[high]) > 0) {
				swap(list, low, high);
			}
			return;
		}

		int l = low;
		int h = high;
		T pivot = list[(l + h) / 2];
		list[(l + h) / 2] = list[h];
		list[h] = pivot;
		while (l < h) {
			while (list[l].compareTo(pivot) <= 0 && l < h) {
				l++;
			}
			while (pivot.compareTo(list[h]) <= 0 && l < h) {
				h--;
			}
			if (l < h) {
				swap(list, l, h);
			}
		}
		list[high] = list[h];
		list[h] = pivot;

		quickSort(list, low, l - 1);
		quickSort(list, h + 1, high);
	}

	/**
	 * Use the FastQuickSort algorithm to sort the array <code>list</code>
	 * array in ascending order.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @return the sorted array
	 */
	public static <T extends Comparable<? super T>> T[] fastQuickSort(T[] list) {
		fastQuickSort(list, 0, list.length - 1);
		insertionSort(list, 0, list.length - 1);

		return list;
	}

	/**
	 * The recursive function used by the FastQuickSort algorithm. Sort with
	 * array length greater than 4 only.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @param l
	 * @param r
	 */
	protected static <T extends Comparable<? super T>> void fastQuickSort(
			T[] list, int l, int r) {
		final int M = 4;
		int i;
		int j;
		T v;
		if ((r - l) > M) {
			i = (r + l) / 2;
			if (list[l].compareTo(list[i]) > 0) {
				swap(list, l, i);
			}
			if (list[l].compareTo(list[r]) > 0) {
				swap(list, l, r);
			}
			if (list[i].compareTo(list[r]) > 0) {
				swap(list, i, r);
			}

			j = r - 1;
			swap(list, i, j);
			i = l;
			v = list[j];
			while (true) {
				while (list[++i].compareTo(v) < 0)
					;
				while (list[--j].compareTo(v) > 0)
					;
				if (j < i)
					break;

				swap(list, i, j);
			}
			swap(list, i, r - 1);

			fastQuickSort(list, l, j);
			fastQuickSort(list, i + 1, r);
		}
	}

	/**
	 * Use the InsertionSort algorithm to sort the array <code>list</code>
	 * array in ascending order.
	 * 
	 * @param list
	 *            the array to be sorted
	 */
	protected static <T extends Comparable<? super T>> void insertionSort(
			T[] list, int low, int high) {
		int i;
		int j;
		T v;
		for (i = low + 1; i <= high; i++) {
			v = list[i];
			j = i;
			while ((j > low) && (list[j - 1].compareTo(v) > 0)) {
				list[j] = list[j - 1];
				j--;
			}
			list[j] = v;
		}
	}

	/**
	 * Use the DoubleStorageMergeSort algorithm to sort the array
	 * <code>list</code> array in ascending order.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @return the sorted array
	 */
	public static <T extends Comparable<? super T>> T[] doubleStorageMergeSort(
			T[] list) {
		T[] scratch = list.clone();
		doubleStorageMergeSort(list, 0, list.length - 1, scratch);

		return list;
	}

	/**
	 * The recursive function used by the DoubleStorageMergeSort algorithm.
	 * 
	 * @param list
	 *            the array to be sorted
	 * @param l
	 * @param h
	 * @param scratch
	 *            temperate storage array
	 */
	protected static <T extends Comparable<? super T>> void doubleStorageMergeSort(
			T[] list, int low, int high, T[] scratch) {
		if (low >= high)
			return;

		int mid = (low + high) / 2;
		doubleStorageMergeSort(list, low, mid, scratch);
		doubleStorageMergeSort(list, mid + 1, high, scratch);

		int l = low;
		int h = mid + 1;
		for (int k = low; k <= high; k++) {
			if ((l <= mid) && ((h > high) || (list[l].compareTo(list[h]) < 0))) {
				scratch[k] = list[l++];
			} else {
				scratch[k] = list[h++];
			}
		}
		for (int k = low; k <= high; k++) {
			list[k] = scratch[k];
		}
	}

}
